/* 
 *  Copyright (c) 2012 Shirou Maruyama
 * 
 *   Redistribution and use in source and binary forms, with or without
 *   modification, are permitted provided that the following conditions
 *   are met:
 * 
 *   1. Redistributions of source code must retain the above Copyright
 *      notice, this list of conditions and the following disclaimer.
 *
 *   2. Redistributions in binary form must reproduce the above Copyright
 *      notice, this list of conditions and the following disclaimer in the
 *      documentation and/or other materials provided with the distribution.
 *
 *   3. Neither the name of the authors nor the names of its contributors
 *      may be used to endorse or promote products derived from this
 *      software without specific prior written permission.
 */

#include <vector>
#include <iostream>
#include <deque>
#include <cmath>
#include <stdint.h>
#include "pacbeep.hpp"
#include "dictionary.hpp"

using namespace std;

namespace pacbeep {

  NODE dequeue(deque<NODE>& q) {
    NODE x = q[0];
    q.pop_front();
    return x;
  }

  uint64_t power(int64_t base, int64_t index) {
    if (index == 0) return 1ULL;
    if (index & 1LL) return base * power(base, index - 1);
    else {
      uint64_t x = power(base, index / 2);
      return x * x;
    }
  }

  uint64_t ComputeVal(const NODE& left, const NODE& right) {
    return left.val + right.val * power(kPrime, left.len) & 0xFFFFFFFFFFFFFFFFULL;
  }

  uint64_t ComputeLCAd(const uint64_t i, const uint64_t j) { 
    uint64_t Ni = 2*i - 1;
    uint64_t Nj = 2*j - 1;
    uint64_t x = Ni ^ Nj;
    x = (uint64_t)floor(log2((double)x));
    return x;
  }

  void PACBEEP::Init(uint32_t k) {
    vector<deque<NODE> >(kMaxNumQue).swap(Queues_);
    for (uint32_t i = 0; i != kMaxNumQue; ++i) {
      Queues_[i].push_back(NODE());
    }
    NumQue_ = 0;
    Dict_.Init(k);
  }

  void PACBEEP::InsertChar(uint8_t ch, ostream& os) {
    GrammarTrans(NODE(ch), 0, os);
  }

  void PACBEEP::Flush(ostream& os) {
    uint32_t level = 0;
    while (Queues_[level].size() >= 3) {
      dequeue(Queues_[level]);
      while (Queues_[level].size() >= 2) {
	NODE x1 = dequeue(Queues_[level]);
	NODE x2 = dequeue(Queues_[level]);
	NODE v  = ReplaceCodes(x1, x2, os);
	GrammarTrans(v, level + 1, os);
      }
      if (Queues_[level].size() == 1) {
	NODE x1 = dequeue(Queues_[level]);
	GrammarTrans(x1, level + 1, os);
      }
      ++level;
    }
  }

  NODE PACBEEP::ReplaceCodes(const NODE& x1, const NODE& x2, ostream& os) {
    NODE node;
    if (!(Dict_.GetCode(x1.code, x2.code, node.code))) {
      ++NumRules_;
      os.write((char*)&(x1.code), sizeof(x1.code));
      os.write((char*)&(x2.code), sizeof(x2.code));
    }
    node.val = ComputeVal(x1, x2);
    node.len = x1.len + x2.len;
    return node;
  }
  
  bool PACBEEP::IsRepetition(uint32_t level, uint32_t pos) const {
    uint64_t w1 = Queues_[level][pos    ].val;
    uint64_t w2 = Queues_[level][pos + 1].val;
    if (w1 == w2) return true;
    return false;
  }
  
  bool PACBEEP::IsMinimal(const uint32_t level, const uint32_t pos) const {
    uint64_t w0 = Queues_[level][pos - 1].val;
    uint64_t w1 = Queues_[level][pos    ].val;
    uint64_t w2 = Queues_[level][pos + 1].val;
    if ((w0 > w1) && (w1 < w2)) return true;
    return false;
  }

  bool PACBEEP::IsMaximal(const uint32_t level, const uint32_t pos) const { 
    uint64_t w0 = Queues_[level][pos - 1].val;
    uint64_t w1 = Queues_[level][pos    ].val;
    uint64_t w2 = Queues_[level][pos + 1].val;
    uint64_t w3 = Queues_[level][pos + 2].val;
    
    if (!(w0 < w1 && w1 < w2 && w2 < w3) &&
	!(w0 > w1 && w1 > w2 && w2 > w3)) return false;

    if (ComputeLCAd(w1,w2) > ComputeLCAd(w0,w1) &&
        ComputeLCAd(w1,w2) > ComputeLCAd(w2,w3)) return true;

    return false;
  }
  
  bool PACBEEP::IsPair(const uint32_t level) const {
    if (IsRepetition(level, 1))
      return true;
    else if (IsRepetition(level, 2))
      return false;
    else if (IsRepetition(level, 3))
      return true;
    else if (IsMinimal(level, 1) || IsMaximal(level, 1))
      return true;
    else if (IsMinimal(level, 2) || IsMaximal(level, 2))
      return false;
    return true;
  }

  void PACBEEP::GrammarTrans(const NODE& node, uint32_t level, ostream& os) {
    Queues_[level].push_back(node);
    if (Queues_[level].size() >= kMaxQueLen) {
      if (IsPair(level) == true) {
	dequeue(Queues_[level]);
	NODE x1 = dequeue(Queues_[level]);
	NODE x2 = Queues_[level][0];
	NODE v  = ReplaceCodes(x1, x2, os);
	GrammarTrans(v, level + 1, os);
      }
      else {
	dequeue(Queues_[level]);
	NODE x1 = dequeue(Queues_[level]);
	GrammarTrans(x1, level + 1, os);
	NODE x2 = dequeue(Queues_[level]);
	NODE x3 = Queues_[level][0];
	NODE v  = ReplaceCodes(x2, x3, os);
	GrammarTrans(v, level + 1, os);
      }
    }
  }
} // namespace pacbeep

